# -*- coding: utf-8 -*-
# 快速排序

def quick_sort(array):
    return qsort(array, 0, len(array) - 1)


def qsort(array, left, right):
    if left >= right:
        return array
    value = array[left]  # 取最左边的为基准数
    lp = left  # 左指针
    rp = right  # 右指针
    while lp < rp:
        while array[rp] >= value and lp < rp:
            rp -= 1
        while array[lp] <= value and lp < rp:
            lp += 1
        array[lp], array[rp] = array[rp], array[lp]  # 调换位置
    array[left], array[lp] = array[lp], array[left]
    qsort(array, left, lp - 1)
    qsort(array, rp + 1, right)
    return array
